#include <stdio.h>
#include <stdlib.h>

/*
 * 参考 青岛大学--王卓 的课程
 * 地址 https://www.bilibili.com/video/av32334555/?spm_id_from=333.788.videocard.0
 * */
#define Error '0';
#define Ok '1';
typedef char ElementType;
typedef struct LNode {
    ElementType data;
    struct LNode *next;
} LNode, *LinkList;

void InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));
    L->next = NULL;
}

// 头插法建立链表
void CreateList_H(LinkList &L, ElementType e) {
    LNode *p;
    p = (LNode *) malloc(sizeof(LNode));
    p->data = e;

    // 头插入法核心代码 --start
    p->next = L->next;
    L->next = p;
    // 头插入法核心代码 --end
}

// 尾插法建立链表
void CreateList_R(LinkList &L, ElementType e) {
    LNode *newPoint, *p = L;
    newPoint = (LNode *) malloc(sizeof(LNode));
    newPoint->data = e;
    newPoint->next = NULL;

    // 尾插入法核心代码 --start
    // 找到尾节点
    while (p->next) {
        p = p->next;
    }
    p->next = newPoint;
    // 尾插入法核心代码 --end
}

// 尾插入法在任意位置插入
int ListInsert(LinkList &L, int i, ElementType e) {
    int j = 0;
    LNode *p = L, *newPoint;
    while (j < i - 1 && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL) {
        return 0;
    } else {
        newPoint = (LNode *) malloc(sizeof(LNode));
        newPoint->data = e;
        newPoint->next = p->next;
        p->next = newPoint;
        return 1;
    }
}

// 求链表的表长
int ListLength_L(LinkList L) {
    LinkList p;
    int length = 0;

    p = L->next;
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

// 清空单链表 : 清空单链表的内容，但是保留头结点和头指针
void ClearList(LinkList &L) {
    LNode *p, *q;
    p = L->next;
    while (p) {
        q = p->next;
        free(q);
        p = q;
    }
    L->next = NULL;
}

// 销毁单链表 : 销毁链表的所有元素 && 销毁头结点和头指针
void DestroyList(LinkList &L) {
    LNode *p;
    while (L) {
        p = L;
        L = L->next;
        free(p);
    }
}

// 取第i个元素值
ElementType GetItem(LinkList L, int i) {
    LNode *p = L->next;
    int j;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j > i) {
        return Error;
    }
    return p->data;
}

// 单链表的按值查找 : 按照置查找，返回地址
LNode *LocateItem(LinkList L, ElementType e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}

// 展示单链表
void DisList(LinkList L) {
    LNode *p = L->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

void TestSingleLinkList() {
    LinkList L; // 指向结构体的指针
    ElementType e;
    printf("初始化单链表\n");
    InitList(L);

//    printf("测试头插入法插入a,b,c,d");
//    // 头插入法的插入顺序是倒序的
//    CreateList_H(L, 'd');
//    CreateList_H(L, 'c');
//    CreateList_H(L, 'b');
//    CreateList_H(L, 'a');

    printf("测试尾插入法插入a,b,c,d");
    // 尾插入法的插入顺序是顺序的
    CreateList_R(L, 'a');
    CreateList_R(L, 'b');
    CreateList_R(L, 'c');
    CreateList_R(L, 'd');

    printf("输出单链表\n");
    DisList(L);

    printf("\n");
    printf("链表的长度是%d\n", ListLength_L(L));

//    printf("******************");
//    printf("清空单链表\n");
//    ClearList(L);
//    printf("输出清空单链表后的单链表\n");
//    DisList(L);
//    printf("再次插入一个值\n");
//    CreateList_R(L, 'e');
//    printf("输出单链表\n");
//    DisList(L);
//
//    printf("\n");
//    printf("******************");
//    printf("销毁单链表\n");
//    DestroyList(L);
//    printf("验证头结点的指针L已经为NULL%d\n", L==NULL);
//    printf("再次插入一个值\n"); // 可以看到不运行后面的了,说明头结点的指针L已经被删除了
//    CreateList_R(L, 'f');
//    printf("输出单链表\n");
//    DisList(L);

    printf("查找第1个位置的值=%c\n", GetItem(L, 1));
    printf("查找第2个位置的值=%c\n", GetItem(L, 2));
    printf("查找第3个位置的值=%c\n", GetItem(L, 3));
    printf("查找第4个位置的值=%c\n", GetItem(L, 4));

    printf("*********\n");
    printf("查找第a位置的值=%c\n",LocateItem(L,'a')->data);
    printf("查找第b位置的值=%c\n",LocateItem(L,'b')->data);
    printf("查找第c位置的值=%c\n",LocateItem(L,'c')->data);
    printf("查找第d位置的值=%c\n",LocateItem(L,'d')->data);

//    printf("采用尾插入法插入a,b,c,d元素\n");
//    ListInsert(L, 1, 'a');
//    ListInsert(L, 2, 'b');
//    ListInsert(L, 3, 'c');
//    ListInsert(L, 4, 'd');
}

